import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> stackMin = new Stack<>();
    public MinStack() {

    }
    
    public void push(int val) {
        stack.push(val);
        if (stackMin.isEmpty()) {
            stackMin.push(val);
        }else {
            if (val <= stackMin.peek()) {
                stackMin.push(val);
            }
        }
    }
    
    public void pop() {

        if (stackMin.peek().equals(stack.peek())) {
            stackMin.pop();
        }
        stack.pop();

    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return stackMin.peek();
    }
}
//括号匹配
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' ||s.charAt(i) == '[' ||s.charAt(i) == '{') {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return false;
                } else {
                    char ret = stack.pop();
                    if (!(s.charAt(i) == ')' && ret == '(' ||s.charAt(i) == '}' && ret == '{' ||s.charAt(i) == ']' && ret == '[')) {
                        return false;
                    }
                }
            }
        }
        return  stack.isEmpty();
    }
}
class Solution1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        int i = 0;
        int j = 0;
        Stack<Integer> stack = new Stack<>();
        while (i < pushV.length) {
            if (stack.isEmpty() || stack.peek() != popV[j]) {
                stack.push(pushV[i]);
            }
            while (j < popV.length && !(stack.isEmpty()) && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
            i++;
        }
        return stack.isEmpty();
    }
}


class MyStack {
    public Queue<Integer> queue1 = new LinkedList<>();
    public Queue<Integer> queue2 = new LinkedList<>();
    public MyStack() {

    }

    public void push(int x) {
        if(empty()) {
            queue1.offer(x);
            return;
        }
        if(queue1.isEmpty()) {
            queue2.offer(x);
        } else {
            queue1.offer(x);
        }
    }

    public int pop() {
        if(queue1.isEmpty()) {
            int size = queue2.size();
            for(int i = 0;i < size-1;i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }else {
            int size = queue1.size();
            for(int i = 0;i < size-1;i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }
    }

    public int top() {
        int ret = 0;
        if(queue1.isEmpty()) {
            int size = queue2.size();
            for(int i = 0;i < size;i++) {
                ret = queue2.poll();
                queue1.offer(ret);
            }
        }else {
            int size = queue1.size();
            for(int i = 0;i < size;i++) {
                ret = queue1.poll();
                queue2.offer(ret);
            }
        }
        return ret;
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}